package sorts;


public class QuickSort {

    static int swapCount = 0;

    public static void quickSort(int[] args){
        if(args== null || args.length <=1){
            return;
        }

        int len = args.length;
        qSort(args,0, len -1);
    }

    //swap count less
    private static void qSort(int[] args, int start, int end){
        if(start == end){
            return;
        }
        int v = args[start];
        int i = start + 1;
        int j = end;
        while(i < j){
            while(i <= end && args[i] < v ){
                i++;
            }
            while(j >= start && args[j] >= v){
                j --;
            }
            if (i < j) {

                int t = args[i];
                args[i] = args[j];
                args[j] = t;
                swapCount ++;
            }
        }
        if(i != start + 1){
            args[start] = args[i - 1];
            args[i-1] = v;
            swapCount ++;
        }

//        print(args);
        if(i > start + 1){
            qSort(args, start, i - 2);
        }
        if( j < end){
            qSort(args, i, end);
        }
    }

    //swapCount more
    public static int[] qsort(int arr[],int start,int end) {
        int pivot = arr[start];
        int i = start;
        int j = end;
        while (i<j) {
            while ((i<j)&&(arr[j]>pivot)) {
                j--;
            }
            while ((i<j)&&(arr[i]<pivot)) {
                i++;
            }
            if ((arr[i]==arr[j])&&(i<j)) {
                i++;
            } else {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                swapCount ++;
            }
        }
//        print(arr);
        if (i-1>start) {arr=qsort(arr,start,i-1);}
        if (j+1<end) {arr=qsort(arr,j+1,end);}
        return (arr);
    }
    static int count = 0;
    public static void print(int[] nums){
        for(int i: nums) {
            System.out.print(i + ",");
        }
        System.out.println();
        count ++;
    }

    public static void main(String[] args){
        int[] nums = new int[]{10,3,3,3,7,9,122344,4656,34,34,4656,5,6,7,8,9,343,57765,23,12321};
        QuickSort.quickSort(nums);
//        nums = QuickSort.qsort(nums, 0, nums.length - 1);
        print(nums);
        System.out.println(swapCount);
//        System.out.println(count);
    }
}
